Computers are used in many applications. As computing systems continue to evolve, the graphical display requirements of the systems become more demanding. This is especially true in applications where three-dimensional graphic displays must be updated quickly. One example of such an application is a computer game where movement and modification of background images may place great demands on the processing power of the computing system.
In order to display some screen images, detailed textures are stored in memory. These textures are then filtered and adapted to map to structures or graphic primitives for subsequent display. An example is a brick pattern that can be mapped onto a wall structure. If the wall is extending into the distance, then the texture will be mapped in such a way to show perspective. In other examples, shadow maps are used to provide shadows to rendered graphics. Shadow maps are textures where each texel in the texture represents a depth value indicating at what distance the light hits a surface. In such a manner, texture mapping adds realism to the computer-generated graphic.
In shadow mapping, adequate sampling of the shadow map poses two sequential and interdependent rendering problems. First, the pixel depths of a scene must be rendered at an adequate resolution from the light's point of view. Second, the main shadow texture must be adequately sampled to render the scene using the sampled shadow map. Because the scene complexity may vary, the use of a single shadow map sampled at one sampling rate may result in using various texel-to-pixel ratios for different portions of the screen. The texel-to-pixel ratio is indicative of the number of texels that map to a particular pixel being rendered. In other words, while the resolution of the shadow map may be adequate for some portions of the scene, the shadow map is in minification mode for other regions of the scene. One of ordinary skill will recognize that minification mode corresponds to a mapping mode wherein multiple texels map to one pixel. When rasterizing portions of the scene where the shadow map is in minification mode, the memory access pattern within the texture is fairly sparse, i.e., the memory access pattern is not localized in a small region in a texture, resulting in poor texture cache coherency. Put another way, because a region in the shadow map may map to several different regions of the scene, the number of memory accesses is large and certain regions of the texture may be accessed several times with each access possibly causing a cache miss. Thus, texture bandwidth requirements are increased.
Those having ordinary skill in the art will recognize that mip maps have been utilized to facilitate the use of textures in texturing operations. Mip maps are pre-calculated, optimized collections of two-dimensional or three-dimensional images associated with a main texture stored in computer memory for access when rendering. In some instances, mip maps are stored in texture cache memory for quick access by a video graphics engine. By employing multiple, scaled versions of a texture during rendering operations, processing requirements and visual artifacts in the rendered image are reduced while execution speed of the application (i.e., the rendering speed) is increased. The reduction of aliasing artifacts is attributed to, among other things, the use of pre-filtered, lower resolution images (i.e., mip maps) generated from the original texture. The execution speed is attributed to, among other things, reducing unnecessary texture bandwidth by replacing a sparse sequence of fetches on a single, high resolution texture with a more dense sequence of fetches on a more localized region of smaller textures (i.e., mip maps) thus improving cache coherency. In other words, the number of memory accesses is reduced.
Typically, mip maps associated with a main texture are categorized as part of a mip map chain consisting of several mip maps where each mip map corresponds to a particular level. The top level mip map may be the main texture itself or any other suitable version thereof and each successive mip map located below it in the chain is derived from its parent, i.e., the mip map located directly above it. Thus, successive mip maps each have less detail than its parent. Generally, each mip map level in the chain is one-quarter the size of its parent. For instance, the first mip map in the chain may have a resolution of 512×512. The next mip map in the chain may have a resolution of 256×256. The third mip map in the chain may have a resolution of 128×128, etc. Accordingly, based on the structure or graphics primitive on a screen, the computer can select a suitable mip map having the appropriate level of detail to perform texture operations in order to increase processing speed. Using a low mip map level on the chain translates into using a smaller mip map having less detail than the main texture, thus saving processing resources.
While a variety of techniques may be used to generate mip map chains for all types of textures, two prior art techniques are described below for purposes of example only. Non-shadow map mip maps, such as color texture maps, are commonly generated by filtering and downsampling its parent mip map. Generally, filtering is performed by taking, for each mip map texel, the average of its four parent texels. Filtering a shadow map, however, is not beneficial because taking the average of a texel's four parent texels biases at least one texel of the shadow map toward the light source. In other words, because shadow map texels represent depth values, the average depth value of four texels may be a smaller value than one or more of the parent texels. A smaller depth value results in the region appearing closer to the light source than the furthest depth value. Instead, it is beneficial to use the max depth value of the four patent texels to generate each mip map texel. This results in an image with a less undesirable artifacts because the region is never closer to the light source. While additional erroneous, self shadowing is reduced, the side effect of using the max depth value is that shadows are reduced in size when rendered.
The current approach used by video graphics engines select a mip map level according to a variety of selection schemes including a max-axis selection scheme and an anisotropic filtering mip map level selection scheme. Generally, prior art selection schemes first generate or determine the texture space derivatives of the texture coordinates with respect to screen space for a given pixel being rendered. Because screen space coordinates are generally represented as (x, y) and because texture space coordinates are generally represented as (u, v), vectors (∂u/∂x,∂v/∂x) and (∂u/∂y,∂v/∂y) may be identified using these derivatives that represent the projection of the pixel's edges in texture space for the current pixel and texel location. In other words, the vectors defined above approximate the pixel's footprint in texture space. A pixel footprint in texture space may take any suitable shape. For example, the footprint may be long and narrow when surfaces are viewed at oblique angles. Accordingly, the lengths of the pixel's edges in texture space may vary greatly according to the vectors provided above.
To select a mip map according to the max-axis mip map level selection scheme, where the selected mip map level, miplevelmax, is determined according to the following equations:
                    xAxis        2            =                                    (                                          ∂                u                                            ∂                x                                      )                    2                +                              (                                          ∂                v                                            ∂                x                                      )                    2                      ;                      yAxis        2            =                                    (                                          ∂                u                                            ∂                y                                      )                    2                +                              (                                          ∂                v                                            ∂                y                                      )                    2                      ;                      miplevel        max            =              0.5        *                              log            2                    ⁡                      (                          max              ⁡                              (                                                      xAxis                    2                                    ,                                      yAxis                    2                                                  )                                      )                                ;  
wherein xAxis2 corresponds to the summation of the squares of the texture space derivatives with respect to the x-axis of screen space and wherein yAxis2 corresponds to the summation of the squares of the texture space derivatives with respect to the y-axis of screen space. In this example, the max-axis corresponds to the greater of the xAxis2 and the yAxis2. The above scheme is generally utilized where the texture data fetched using the max-axis mip map level selection scheme is filtered using an isotropic filtering scheme. As known in the art, isotropic filtering schemes may include or incorporate, for example, bilinear texture filtering, trilinear texture filtering, nearest texture sampling, or bicubic texture filtering.
The max-axis mip map level selection scheme chooses the max-axis (i.e., the longest pixel edge in texture space), represented by the equation max(xAxis2, yAxis2). Use of the max-axis to select a mip map level generally results in a reduction in the number of aliasing artifacts present in the rendered image for most texture maps. While aliasing is reduced, the rendered image may appear blurred due to the manner in which mip map chains are constructed as downsampled versions of the original main texture. The max-axis scheme is used for most texture operations because aliasing artifacts have a greater adverse effect on the quality of the rendered image than portions thereof which appear blurry.
Another related technique for selecting a mip map level utilizes an anisotropic filtering mip map level selection scheme based on at least one of a max-axis based mip map level, an amount of anisotropy and a min-axis based mip map level. In one type of anisotropic filtering, the mip map level, miplevelaniso, is determined according to the following equations:miplevelmin=0.5*log2(min(xAxis2,yAxis2));miplevelaniso=max(miplevelmax−log2(mxaniso),miplevelmin);wherein miplevelmax, xAxis2, and yAxis2 are determined according to the equations previously presented. The variable mxaniso represents an amount or degree of anisotropy desired and is generally predetermined based on the capability of the computing system and/or the application running on the computer system. In one embodiment, mxaniso is stored in a register or any other suitable memory structure or structures for use by the computer system or video graphics engine. While the equation above provides one example of selecting a mip map level based on an amount of anisotropy, one of ordinary skill in the art will recognize that other suitable equations could be used when in an anisotropic filtering mode. In anisotropic texture filtering, the mip map level may be selected at a few levels higher than in the max-axis mip map level selection scheme in anticipation of multiple samples being taken and filtered. However, in the case of anisotropic filtering, the number of mip map levels above the max-axis selected level is limited by the number of texture samples taken in the anisotropic filters since aliasing artifacts remain an issue due to the nature of the anisotropic filtering algorithm.
In the context of shadow mapping, however, neither selection scheme adequately reduces the number of artifacts in the rendered image. Using a shadow map in texture mapping differs from the application of standard texture maps (i.e., non-shadow map texture maps such as color texture maps) in that selecting a mip map level low in the mip map chain is equivalent to undersampling the scene in shadow map space. Thus, when applying a shadow map to a surface or primitive, aliasing artifacts result where a single texel maps to several screen pixels. The effect is most visible where a shadow projected on a surface is viewed at an oblique angle, thus causing a single texel to map to several screen pixels. This happens to correspond to the situation where the difference between xAxis2 and yAxis2 is large.
FIG. 1 illustrates the effect the application of the max-axis mip map level selection scheme has on a rendered scene 100 when the texture applied to the video graphics primitives is a shadow map. As illustrated, the scene includes a background 102, a floor 104, a first pillar 106, a second pillar 108 and a light source 110. As expected, the light source 110 causes a first shadow 112 associated with the first pillar 106 and a second shadow 114 associated with the second pillar 108. Aliased artifacts 116 adversely affect the quality of the rendered scene 100 by extending the color or other pixel parameters of the floor 104 onto pixel locations that should be associated with the first and second shadows 112 and 114. Similarly, aliased artifacts 118 adversely affect the quality of the rendered scene 100 by improperly extending the first and second shadows 112 and 114 onto locations on the floor 104 that should not be in shadow.
Thus, a need exists for a mip map level selection scheme that prevents aliased artifacts in a rendered scene when a texture map, such as for example a shadow map, is applied to structures or graphics primitives. A similar need exists for a mip map level selection scheme designed to prevent a texel from mapping to more than one pixel where the main texture is of sufficient resolution.